# RBTree : Red black tree

This module is a red-black tree library. A red-black tree is a type of binary search tree. It is self balancing like the AVL tree, though it uses different properties to maintain the invariant of being balanced.

User can use the following code to import the RBTree module.

var RBTree = require('rbtree');

# Support

The following shows RBTree module APIs available for each permissions.

# RBTree Class

# new RBTree(cmp)

• cmp {Function} compare function.
• Returns: {Object} rms object.

Create a red-black tree object, cmp is a funtion to compare your keys to determine ordering. The function will take two of your key type (whatever that will be) and return -1, 0, xor 1. For cmp(a, b), it returns -1 if a < b, 0 if a == b and 1 if a > b.

# Example

var tree = new RBTree(function(k1, k2) {
  if (k1 < k2) 
    return -1;
  else if (k1 > k2)
    return 1;
  else
    return 0;
});

# RBTree Object

# tree.put(key, value)

• key {Any} New node key.
• value {Any} New node value.

Insert key:value pair. It will over-write a pre-existed entry for key.

# Example

tree.put(1, 'Han.hui');
tree.put(2, 'Zhang.san');

# tree.get(key)

• key {Any} Node key.
• Returns: {Any} The value of the previously inserted by key.

Get the value specified by key.

# Example

var name = tree.get(1);

# tree.exists(key)

• key {Any} Node key.
• Returns: {Boolean} true if exist, false otherwise.

Determine if a key exists in the tree.

# tree.delete(key)

• key {Any} Node key.
• Returns: {Boolean} true if deleted, false otherwise.

Delete the node specified by key.

# Example

tree.delete(2);

# tree.deleteLeast()

• Returns: {Array} Index 0 is key, index 1 is value.

Find the least node, delete it and return the node's [key, value] pair.

# tree.deleteGreatest()

• Returns: {Array} Index 0 is key, index 1 is value.

Find the greatest node, delete it and return the node's [key, value] pair.

# tree.inorder(fn[, reverse])

• fn {Function} Visit callback function.
• reverse {Boolean} Whether to traverse backwards.

Visit each node in-order an call a function on the (key,data).

# Example

var RBTree = require('rbtree');

var tree = new RBTree(function(k1, k2) {
  if (k1 < k2) 
    return -1;
  else if (k1 > k2)
    return 1;
  else
    return 0;
});

tree.put(1, 'Han.hui');
tree.put(2, 'Zhang.san');

tree.inorder(function(key, value) {
  console.log('ID:', key, 'NAME:', value);
});